package com.mdnote.practice.devide_and_rule;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/16
 * @description  电话号码的字母组合
 */
public class LeetCode17 {

    public static void main(String[] args) {
        LeetCode17 leetCode17 = new LeetCode17();
        leetCode17.letterCombinations("23");
    }

    public List<String> letterCombinations(String digits) {

        if (digits.length() == 0) {
            return new ArrayList<>();
        }

        String[] lettersArray = {
                "",
                "",
                "abc",
                "def",
                "ghi",
                "jkl",
                "mno",
                "pqrs",
                "tuv",
                "wxyz"
        };

            // recursion
    //        List<String> resList = new ArrayList<>();
    //        recursion(0, "", resList, digits, lettersArray);
    //        resList.forEach(System.out::println);

            // queue
            List<String> resList = new ArrayList<>();
            resList = queue(lettersArray, digits);
            resList.forEach(System.out::println);

            return resList;
    }

    private List<String> queue(String[] lettersArray, String digits) {
        LinkedList<String> queue = new LinkedList<>();
        queue.addLast("");
        for (int i = 0; i < digits.length(); i++) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                String letters = lettersArray[digits.charAt(i) - 48];
                String temp = queue.removeFirst();
                for (int k = 0; k < letters.length(); k++) {
                    queue.addLast(temp + letters.charAt(k));
                }
            }
        }
        return queue;
    }

    private void recursion(int level, String res, List<String> resList, String digits, String[] letterArray) {
        // Terminator
        if (level == digits.length()) {
            resList.add(res);
            return;
        }
        // device big problem
        String letters = letterArray[digits.charAt(level) - 48];
        for (int i = 0; i < letters.length(); i++) {
            recursion(level + 1, res + letters.charAt(i), resList, digits, letterArray);
        }
    }
}
